package ebook.datastructure.typed.chapter7;

import Algorithms.classic.SortUtils;

/**
 * description: <br>
 * createTime: 2018/11/811:13 <br>
 *
 * @author zzh
 */
public class RadixSort {

    private static final int RADIX_DEFAULT = 10;

    public static int[] radixSort(int[] array) {
        return radixSort(array, RADIX_DEFAULT);
    }

    public static int[] radixSort(int[] array, int radix) {

        //查出最大值，算出循环次数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
        }
        int loopNum = (int) Math.ceil(Math.log(max)/Math.log(radix));
        NodeList[] nodeLists = new NodeList[radix];
        for (int i = 0; i < radix; i++) {
            nodeLists[i] = new NodeList();
        }
        for (int i = 0; i < loopNum; i++) {
            int divided = (int) Math.pow(radix, i);
            for (int j = 0; j < array.length; j++) {
                int temp = (array[j] / divided) % radix;
                nodeLists[temp].addNode(new RadixSortLinkedNode(array[j]));
            }
            int index = 0;
            for (int j = 0; j < radix; j++) {
                NodeList nodeList = nodeLists[j];
                while(!nodeList.isEmpty()) {
                    array[index++] = nodeList.getOutNode().getValue();
                }
            }
//            System.out.println(Arrays.toString(array));
        }

        return array;
    }


    public static void main(String[] args) {
        int[] array;
        for (int i = 0; i < 10000; i++) {
            array = SortUtils.createRandomArray(10, 100);
            int[] temp = array.clone();
            radixSort(temp);
            boolean result1 = SortUtils.isSorted(temp);
            boolean result2 = SortUtils.equalIgnorePosition(array, temp);
            if (!result1 || !result2) {
                System.out.println("isSorted: " + result1);
                System.out.println("equals: " + result2);
                System.out.println(false);
                System.exit(1);
            }
        }
        System.out.println("over");
    }
}
class NodeList {
    RadixSortLinkedNode first;

    RadixSortLinkedNode last;

    public NodeList() {
    }

    public void addNode(RadixSortLinkedNode node) {
        if(first == null) {
            first= node;
        } else {
            last.next = node;
        }
        last = node;
    }

    public RadixSortLinkedNode getOutNode() {
        RadixSortLinkedNode result = first;
        first = first.next;
        return result;
    }

    public boolean isEmpty() {
        return first == null;
    }
}
class RadixSortLinkedNode {
    private int value;

    RadixSortLinkedNode next;


    public RadixSortLinkedNode(int value) {
        this.value = value;
    }


    public int getValue() {
        return value;
    }


    public RadixSortLinkedNode setValue(int value) {
        this.value = value;
        return this;
    }
}